package com.vincent.algorithms.sort;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，
 * 然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
 * 平均时间复杂度 O(n^2)
 * 最坏情况时间复杂度 O(n^2)
 * 最好情况时间复杂度 O(n^2)  主要是因为这种方式没有短路操作
 * 稳定性 不稳定
 * 排序方式 内部排序
 * 空间复杂度 O(1)
 * Created by yangwenchang on 2017/8/22.
 */
public class SelectSort implements Sort {

    public  <T> void sort(T[] array, Comparator<? super T> c) {
        int swapCount = 0;
        int compareCount = 0;

//          表示在选择第几小的元素 0...i-1下标的元素 肯定都是更小的
//          前面都是有序的 而且都是比后面未排序的数据更小
        for (int i = 0; i < array.length; i++) {
            int index = i;
//              这里的是在剩下的元素中选择最小的
            for (int j = i + 1; j < array.length; j++) {
                compareCount++;
                if (c.compare(array[index], array[j]) > 0) {
                    swapCount++;
                    index = j;
                }
            }
//            不相等时表示需要交换
            if (index != i) {
                Sort.swap(array, index, i);
            }
        }

        System.out.println("总计交换次数:" + swapCount);
        System.out.println("总计比对次数:" + compareCount);

    }

    public static void main(String[] args) {

        Integer[] arr = {1, 5, 4, 6, 9};
        System.out.println(Arrays.asList(arr));
        (new SelectSort()).sort(arr, (x, y) -> x - y);
        System.out.println(Arrays.asList(arr));

    }
}
